package algorithm.difficult;

import java.util.Arrays;

/**
 * 给你一个整数n，请你帮忙统计一下我们可以按下述规则形成多少个长度为n的字符串：
 *
 * 字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
 * 每个元音'a'后面都只能跟着'e'
 * 每个元音'e'后面只能跟着'a'或者是'i'
 * 每个元音'i'后面不能 再跟着另一个'i'
 * 每个元音'o'后面只能跟着'i'或者是'u'
 * 每个元音'u'后面只能跟着'a'
 * 由于答案可能会很大，所以请你返回 模10^9 + 7之后的结果。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-vowels-permutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class CountVowelPermutation1220 {
    /**
     * dp[i][j] ,i为当前下标，j为结尾的字符
     *
     */
    public static int countVowelPermutation(int n) {
       long[][] dp = new long[n][5];
       long mod =(long)1e9+7;
        Arrays.fill(dp[0],1);
        for (int i=1;i<n;i++){
            //每个元音'a'后面都只能跟着'e'
            dp[i][1] += dp[i-1][0];
            //每个元音'e'后面只能跟着'a'或者是'i'
            dp[i][0] += dp[i-1][1];
            dp[i][2] += dp[i-1][1];
            //每个元音'i'后面不能 再跟着另一个'i'
            dp[i][0] += dp[i-1][2];
            dp[i][1] += dp[i-1][2];
            dp[i][3] += dp[i-1][2];
            dp[i][4] += dp[i-1][2];
            //每个元音'o'后面只能跟着'i'或者是'u'
            dp[i][2] += dp[i-1][3];
            dp[i][4] += dp[i-1][3];
            //每个元音'u'后面只能跟着'a'
            dp[i][0] += dp[i-1][4];
            for (int j=0;j<5;j++){
                dp[i][j] = dp[i][j]%mod;
            }
        }
        long sum = Arrays.stream(dp[n - 1]).sum()%mod;
        return (int)sum;
    }

    public static void main(String[] args) {
        countVowelPermutation(5);
    }
}
